package hl.alde;

public class Car {
    public static void greedy(int x[], int n ,int k)
    {
        // 检查每相邻两个加油站的距离不超过 n，否则无解
        for(int i=0; i<k; i++)
            if(x[i] > n){
                System.out.println("No solution");
                return ;
            }

        // 一切正常，开始算法
        int count = 1;   // 一共所需加油的次数，出发时必须加油一次
        System.out.println("需要在第 0 个加油站加油一次");
        int distance = 0;// 保存 一次可能最长行驶的距离，累加相邻距离，直到 > n
        for(int i=0; i<k; i++){
            distance += x[i]; // 累加 x[0]~x[i] ，即一次可能最长行驶的距离
            if(distance > n){ // 直到加上x[i]时 一次可能最长行驶的距离 > n   (不加x[i]时，<= n，即中途不用加油)
                count++;      // 加一次油
                distance=x[i];// 以当前 x[i] 为起始点，重新计算distance 一次可能的最长行驶的距离
                System.out.printf("需要在第 %d 个加油站加油一次\n", i);
            }
        }
        System.out.printf("一共需要加油的总次数： %d 次\n", count);
    }

    public static void main(String[] args) {

        int[] x = {30,40,80,12,50};// 初始化 相邻站的距离
        int k = 5;  // 一共的站点数，算上出发站，目的站
        int n = 90; // 加一次油最长行驶的距离

        greedy(x, n ,k);// 调用算法，计算最少的加油次数

    }
}
